# 144.145.94 二叉树的前序遍历
# 给你二叉树的根节点 root ，返回它节点值的 前序、中序、后序 遍历。
#
# 输入：root = [1,null,2,3]
# 输出：[1,2,3] # 前
# 输出：[1,3,2] # 中
# 输出：[3,2,1] # 后

#
# 输入：root = []
# 输出：[]
#
# 输入：root = [1]
# 输出：[1]


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right= None


class Solution:
    def preorderTraversal(self, root):# 前序
        res = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
            else:
                node = stack.pop()
                res.append(node.val)
        return res

    def inorderTraversal(self, root): # 中序
        res = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                res.append(node.val)
        return res

    def postorderTraversal(self, root): # 后序
        res = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                stack.append(node)
                stack.append(None)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                res.append(node.val)
        return res


if __name__ == '__main__':
    a = TreeNode(1)
    b = TreeNode(2)
    c = TreeNode(3)
    a.right = b
    b.left = c
    tmp = Solution()
    # res = tmp.preorderTraversal(a)
    # res = tmp.inorderTraversal(a)
    res = tmp.postorderTraversal(a)
    print(res)
